package leetcode.code2002;

import leetcode.helper.MaxDebug;

/**
 * 执行用时：82 ms, 在所有 Java 提交中击败了69.78%的用户
 *
 * 内存消耗：39.4 MB, 在所有 Java 提交中击败了5.05%的用户
 *
 * 通过测试用例：226 / 226
 *
 * @author CaoYu
 * @date 2021年12月5日
 * @description
 */
public class Solution4 extends S2002 {

	private int range;
	private int len;

	@Override
	public int maxProduct(String s) {
		len = s.length();
		int n = 1 << len;
		range = n - 1;
		Integer[] dp = new Integer[n];
		char[] s1 = new char[len];
		char[] s2 = new char[len];
		return this.f(s.toCharArray(), 0, s1, 0, s2, 0, 0, dp);
	}

	/**
	 * @param charArray 原始字符串
	 * @param index     决定index位置的归属，给s1或者给s2
	 * @param s1        子序列1
	 * @param p1        子序列1当前可用位置
	 * @param s2        相对于子序列1的补序列
	 * @param p2        s2的可用位置
	 * @param dp        记录做过的字符串
	 * @return
	 */
	private int f(char[] charArray, int index, char[] s1, int p1, char[] s2, int p2, int num, Integer[] dp) {
		if (index == charArray.length) {
			String str1 = new String(s1, 0, p1);
			String str2 = new String(s2, 0, p2);
			if (dp[num] != null) {
				return dp[num];
			}
			int len1 = this.longestPalindromeSubseq(str1);
			int len2 = this.longestPalindromeSubseq(str2);
			int ans = len1 * len2;
			dp[num] = ans;
			dp[num ^ range] = ans;
			return ans;
		}
		char c = charArray[index];
		s2[p2] = c;
		int ans1 = this.f(charArray, index + 1, s1, p1, s2, p2 + 1, num, dp);
		s1[p1] = c;
		int ans2 = this.f(charArray, index + 1, s1, p1 + 1, s2, p2, num | 1 << (len - index - 1), dp);
		return Math.max(ans1, ans2);
	}

	/**
	 * s的最长子序列
	 *
	 * @param s
	 * @return
	 */
	public int longestPalindromeSubseq(String s) {
		int Len = s.length();
		if (Len == 0)
			return 0;
		char[] chars = s.toCharArray();
		int[][] dp = new int[Len][Len];
		for (int i = Len - 1; i >= 0; i--) {
			dp[i][i] = 1;
			for (int j = i + 1; j < Len; j++) {
				dp[i][j] = chars[i] == chars[j] ? dp[i + 1][j - 1] + 2 : Math.max(dp[i][j - 1], dp[i + 1][j]);
			}
		}
		return dp[0][Len - 1];
	}

	public static void main(String[] args) {
		Solution4 so = new Solution4();
		so.debug5();
//		so.debug4();
		MaxDebug.debug14(so);
	}

}
